package com.algorithm.base.backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 组合
 *
 * @author Amadeus
 * @date 2023/10/30
 */
public class Combine {

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
        if (k <= 0 || n < k) {
            return list;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        backTracking(n, k, 1, list, queue);
        return list;
    }

    /**
     * 回溯
     *
     * @param n     n
     * @param k     k
     * @param i     我
     * @param list  列表
     * @param queue 队列
     */
    public static void backTracking(int n, int k, int i, List<List<Integer>> list, Deque<Integer> queue) {
        if (queue.size() == k) {
            list.add(new ArrayList<>(queue));
            return;
        }
        for (int j = i; j <= n; j++) {
            queue.add(j);
            backTracking(n, k, j + 1, list, queue);
            queue.removeLast();
        }
    }

    /**
     * 回溯剪枝
     *
     * @param n     n
     * @param k     k
     * @param i     我
     * @param list  列表
     * @param queue 队列
     */
    public static void backTrackingPruning(int n, int k, int i, List<List<Integer>> list, Deque<Integer> queue) {
        if (queue.size() == k) {
            list.add(new ArrayList<>(queue));
            return;
        }
        for (int j = i; j <= n - (k - queue.size()) + 1; j++) {
            queue.add(j);
            backTracking(n, k, j + 1, list, queue);
            queue.removeLast();
        }
    }

    public static void main(String[] args) {
        combine(4, 2);
    }
}
